package com.github.tangmonkmeat;

import java.util.Arrays;

/**
 * Description:
 *
 * @author zwl
 * @version 1.0
 * @date 2021/7/24 上午8:25
 */
public class 信封套娃问题 {

    public static void main(String[] args) {

        int[][] envelopes = new int[][]{{5,4},{6,4},{6,7},{2,3}};
        int maxLen = maxEnvelopes(envelopes);
        System.out.println(maxLen);
    }

    public static int maxEnvelopes(int[][] envelopes) {
        // 对 [w,h] 排序
        // w 按递增顺序
        // w 相同时，h大的在前
        // 最后，只需要找到 h数组中的最长递增子序列即可
        Arrays.sort(envelopes, (a, b) -> a[0] == b[0] ? b[1] - a[1] : a[0] - b[0]);

        int[] h = new int[envelopes.length];
        for (int i = 0;i < envelopes.length;i++){
            h[i] = envelopes[i][1];
        }
        return lengthOfLIS(h);
    }

    public static int lengthOfLIS(int[] a){
        if (a.length <= 1){
            return 1;
        }
        int[] dp = new int[a.length];
        dp[0] = 1;
        int curMaxLen = 1;
        for (int i = 1;i < dp.length;i++){
            dp[i] = 1;
            for (int j = 0;j < i;j++){
                if (a[j] < a[i]){
                    dp[i] = Math.max(dp[i],dp[j] + 1);
                }
            }
            curMaxLen = Math.max(curMaxLen,dp[i]);
        }
        return curMaxLen;
    }

}

